package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.*;

/**
 * 描述：
 * 给你一个整数数组 nums 。如果 nums 的子序列满足下述条件，则认为该子序列是一个 方波 ：
 * <p>
 * 子序列的长度至少为 2 ，并且
 * 将子序列从小到大排序 之后 ，除第一个元素外，每个元素都是前一个元素的 平方 。
 * 返回 nums 中 最长方波 的长度，如果不存在 方波 则返回 -1 。
 * <p>
 * 子序列 也是一个数组，可以由另一个数组删除一些或不删除元素且不改变剩余元素的顺序得到。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-square-streak-in-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author 🧑 ‍wanwei
 * @since 2023-01-13 16:22
 */
public class CR2501 {

    public static void main(String[] args) {
        int[] array = {2,2};
        System.out.println(longestSquareStreak(array));
    }

    //解题思路: 将所有数据开发 直到无法开方下去位置 记录底数及可开方数 将其存入一个map中 最后比较map中列表连续值最长的长度
    public static int longestSquareStreak(int[] nums) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int value = nums[i];
            int length = 0;
            while (true) {
                double valueD = Math.sqrt(value);
                if (valueD % 1 != 0) {
                    List<Integer> set = map.getOrDefault(value, new ArrayList<>());
                    set.add(length);
                    map.put(value, set);
                    break;
                }
                value = (int) valueD;
                length++;
            }
        }

        int length = 0;
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            List<Integer> list = entry.getValue();
            if (list.size() == 1 && length < 1) {
                length = 1;
                continue;
            }
            list.sort(Comparator.naturalOrder());
            int length1 = 1;
            for (int i = 1; i < list.size(); i++) {
                if (list.get(i) - list.get(i - 1) == 1) {
                    length1++;
                    if (length < length1) {
                        length = length1;
                    }
                } else {
                    length1 = 1;
                }
            }
        }

        if(length <= 1){
            return -1;
        }
        return length;
    }
}
